home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 2: Applications / Linux Cubed Series 2 - Applications.iso / circuits / irsim-ca.2 / irsim-ca / irsim-cap-9.2 / src / irsim / nsubrs.c < prev    next >
C/C++ Source or Header  |  1995-05-26  |  11KB  |  480 lines
  1. /* 
  2.  *     ********************************************************************* 
  3.  *     * Copyright (C) 1988, 1990 Stanford University.                     * 
  4.  *     * Permission to use, copy, modify, and distribute this              * 
  5.  *     * software and its documentation for any purpose and without        * 
  6.  *     * fee is hereby granted, provided that the above copyright          * 
  7.  *     * notice appear in all copies.  Stanford University                 * 
  8.  *     * makes no representations about the suitability of this            * 
  9.  *     * software for any purpose.  It is provided "as is" without         * 
  10.  *     * express or implied warranty.  Export of this software outside     * 
  11.  *     * of the United States of America may require an export license.    * 
  12.  *     ********************************************************************* 
  13.  */
  14.  
  15. #include <stdio.h>
  16. #include "defs.h"
  17. #include "net.h"
  18. #include "globals.h"
  19.  
  20. /* useful subroutines for dealing with network */
  21.  
  22. public    char   vchars[] = "0XX1";
  23.  
  24. public    char  *ttype[ NTTYPES ] =
  25.   {
  26.     "n-channel",
  27.     "p-channel",
  28.     "depletion",
  29.     "resistor"
  30.   };
  31.  
  32.  
  33. #define    HASHSIZE        4387    /* hash table size */
  34. #define    NBIT_HASH        14    /* number of bits for HASHSIZE */
  35.  
  36. private    nptr  hash[HASHSIZE];
  37.  
  38.  
  39. public int GetHashSize()
  40.   {
  41.     return( HASHSIZE );
  42.   }
  43.  
  44.  
  45. /* hashing function used in interning symbols */
  46. private    char  lcase[128] = 
  47.   {
  48.     0,        01,    02,    03,    04,    05,    06,    07,
  49.     010,    011,    012,    013,    014,    015,    016,    017,
  50.     020,    021,    022,    023,    024,    025,    026,    027,
  51.     030,    031,    032,    033,    034,    035,    036,    037,
  52.     ' ',    '!',    '"',    '#',    '$',    '%',    '&',    047,
  53.     '(',    ')',    '*',    '+',    ',',    '-',    '.',    '/',
  54.     '0',    '1',    '2',    '3',    '4',    '5',    '6',    '7',
  55.     '8',    '9',    ':',    ';',    '<',    '=',    '>',    '?',
  56.     '@',    'a',    'b',    'c',    'd',    'e',    'f',    'g',
  57.     'h',    'i',    'j',    'k',    'l',    'm',    'n',    'o',
  58.     'p',    'q',    'r',    's',    't',    'u',    'v',    'w',
  59.     'x',    'y',    'z',    '[',    0134,    ']',    '^',    '_',
  60.     '`',    'a',    'b',    'c',    'd',    'e',    'f',    'g',
  61.     'h',    'i',    'j',    'k',    'l',    'm',    'n',    'o',
  62.     'p',    'q',    'r',    's',    't',    'u',    'v',    'w',
  63.     'x',    'y',    'z',    '{',    '|',    '}',    '~',    0177
  64.   };
  65.  
  66.  
  67.  
  68. private int sym_hash( name )
  69.   register char  *name;
  70.   {
  71.     register int  hashcode = 0;
  72.  
  73.     do
  74.     hashcode = (hashcode << 1) ^ (*name | 0x20);
  75.     while( *(++name) );
  76.     return( ((hashcode >= 0) ? hashcode : ~hashcode) % HASHSIZE );
  77.   }
  78.  
  79.  
  80. /*
  81.  * Compare 2 strings, case doesn't matter.  Return value is an integer greater
  82.  * than, equal to, or less than 0, according as 's1' is lexicographically
  83.  * greater than, equal to, or less than 's2'.
  84.  */
  85. public int str_eql( s1, s2 )
  86.   register char  *s1, *s2;
  87.   {
  88.     register int  cmp;
  89.  
  90.     while( *s1 )
  91.       {
  92.     if( (cmp = lcase[*s1++] - lcase[*s2++]) != 0 )
  93.         return( cmp );
  94.       }
  95.     return( 0 - *s2 );
  96.   }
  97.  
  98.  
  99. /* compare pattern with string, case doesn't matter.  "*" wildcard accepted */
  100. public int str_match( p, s )
  101.   register char  *p, *s;
  102.   {
  103.     while( 1 )
  104.       {
  105.     if( *p == '*' )
  106.       {
  107.         /* skip past multiple wildcards */
  108.         do
  109.         p++;
  110.         while( *p == '*' );
  111.  
  112.         /* if pattern ends with wild card, automatic match */
  113.         if( *p == 0 )
  114.         return( 1 );
  115.  
  116.         /* *p now points to first non-wildcard character, find matching
  117.          * character in string, then recursively match remaining pattern.
  118.          * if recursive match fails, assume current '*' matches more...
  119.          */
  120.         while( *s != 0 )
  121.           {
  122.         while( lcase[*s] != lcase[*p] )
  123.             if( *s++ == 0 )
  124.             return( 0 );
  125.         if( str_match( p + 1, ++s ) )
  126.             return( 1 );
  127.           }
  128.  
  129.         /* couldn't find matching character after '*', no match */
  130.         return( 0 );
  131.       }
  132.     else if( *p == 0 )
  133.         return( *s == 0 );
  134.     else if( lcase[*p++] != lcase[*s++] )
  135.         return( 0 );
  136.       }
  137.   }
  138.  
  139.  
  140. /* find node in network */
  141. public nptr find( name )
  142.   register char  *name;
  143.   {
  144.     register nptr  ntemp;
  145.     register int   cmp = 1;
  146.  
  147.     if( txt_coords and name[0] == '@' and name[1] == '=' )
  148.     if( (ntemp = FindNode_TxtorPos( name )) != NULL )
  149.         return( ntemp );
  150.  
  151.     for( ntemp = hash[sym_hash( name )]; ntemp != NULL; ntemp = ntemp->hnext )
  152.       {
  153.     if( (cmp = str_eql( name, ntemp->nname )) >= 0 )
  154.         break;
  155.       }
  156.     return( (cmp == 0) ? ntemp : NULL );
  157.   }
  158.  
  159.  
  160. /*
  161.  * Get node structure.  If not found, create a new one.
  162.  * If create is TRUE a new node is created and NOT entered into the table.
  163.  */
  164. public nptr GetNode( name )
  165.   register char  *name;
  166.   {
  167.     register nptr  n, *prev;
  168.     register int   i;
  169.  
  170.     prev = &hash[ sym_hash( name ) ];
  171.     for( i = 1, n = *prev; n != NULL; n = *(prev = &n->hnext) )
  172.     if( (i = str_eql( name, n->nname )) >= 0 )
  173.         break;
  174.  
  175.     if( i == 0 )
  176.       {
  177.  
  178. /*    if( strcmp( name, n->nname ) != 0 )
  179.         fprintf( stderr, "Warning: Aliasing nodes '%s' and '%s'\n",
  180.           name, n->nname );
  181. */
  182.  
  183.     while( n->nflags & ALIAS )
  184.         n = n->nlink;
  185.     return( n );
  186.       }
  187.  
  188.     /* allocate new node from free storage */
  189.     if( (n = (nptr) freeNodes) == NULL )
  190.     n = (nptr) MallocList( sizeof( struct Node ), 1 );
  191.     freeNodes = n->nlink;
  192.  
  193.     nnodes++;
  194.  
  195.     n->hnext = *prev;    /* insert node into hash table, after prev */
  196.     *prev = n;
  197.  
  198.     /* initialize node entries */
  199.     n->ngate = n->nterm = NULL;
  200.     n->nflags = 0;
  201.     n->ncap = MIN_CAP;
  202.     n->vlow = LOWTHRESH;
  203.     n->vhigh = HIGHTHRESH;
  204.     n->c.time = 0;
  205.     n->tplh = 0;
  206.     n->tphl = 0;
  207.     n->t.cause = NULL;
  208.     n->nlink = NULL;
  209.     n->events = NULL;
  210.     n->npot = X;
  211.  
  212.     n->head.next = last_hist;
  213.     n->head.time = 0;
  214.     n->head.val = X;
  215.     n->head.inp = 0;
  216.     n->head.punt = 0;
  217.     n->head.t.r.rtime = n->head.t.r.delay = 0;
  218.     n->curr = &(n->head);
  219.  
  220.     /* store all node-names as strings */
  221.     i = strlen( name ) + 1;
  222.     n->nname = Valloc( i, 1 );
  223.     bcopy( name, n->nname, i );
  224.  
  225.     n->trans = 0;
  226.     n->trans01 = 0.0;    /* Set 0->1 transition count to zero (PEL 5/3/93) */
  227.  
  228.     n->naliases = 0;    /* Set alias count for node to zero (PEL 5/28/93) */
  229.  
  230.     return( n );
  231.   }
  232.  
  233.  
  234. public nptr GetNewNode( name )
  235.   char  *name;
  236.   {
  237.     register nptr  n;
  238.     int            i;
  239.  
  240.     if( VDD_node != NULL and str_eql( name, pnode( VDD_node ) ) == 0 )
  241.     return( VDD_node );
  242.     if( GND_node != NULL and str_eql( name, pnode( GND_node ) ) == 0 )
  243.     return( GND_node );
  244.  
  245.     if( (n = (nptr) freeNodes) == NULL )
  246.     n = (nptr) MallocList( sizeof( struct Node ), 1 );
  247.     freeNodes = n->nlink;
  248.  
  249.     nnodes++;
  250.  
  251.     n->hnext = n;    /* node NOT inserted in hash-table */
  252.  
  253.     n->ngate = n->nterm = NULL;
  254.     n->nflags = 0;
  255.     n->ncap = MIN_CAP;
  256.     n->vlow = LOWTHRESH;
  257.     n->vhigh = HIGHTHRESH;
  258.     n->c.time = 0;
  259.     n->tplh = 0;
  260.     n->tphl = 0;
  261.     n->t.cause = NULL;
  262.     n->nlink = NULL;
  263.     n->events = NULL;
  264.     n->npot = X;
  265.  
  266.     n->head.next = last_hist;
  267.     n->head.time = 0;
  268.     n->head.val = X;
  269.     n->head.inp = 0;
  270.     n->head.punt = 0;
  271.     n->head.t.r.rtime = n->head.t.r.delay = 0;
  272.     n->curr = &(n->head);
  273.  
  274.     /* store all node-names as strings */
  275.     i = strlen( name ) + 1;
  276.     n->nname = Valloc( i, 1 );
  277.     bcopy( name, n->nname, i );
  278.  
  279.     return( n );
  280.   }
  281.  
  282.  
  283. /* insert node into hash table.  Keep table entry sorted in ascending order */
  284. public void n_insert( nd )
  285.   register nptr  nd;
  286.   {
  287.     register nptr  n, *prev;
  288.     register char  *name;
  289.     register int   i = 1;
  290.  
  291.     name = pnode( nd );
  292.     prev = &hash[ sym_hash( name ) ];
  293.     for( n = *prev; n != NULL; n = *(prev = &n->hnext) )
  294.       {
  295.     i = str_eql( name, n->nname );
  296.     if( i >= 0 )
  297.         break;
  298.       }
  299.     if( i == 0 )
  300.       {
  301.     if( n != nd )
  302.         lprintf( stderr, "n_insert: multiple node '%s'\n", pnode( nd ) );
  303.     return;
  304.       }
  305.     nd->hnext = *prev;
  306.     *prev = nd;
  307.   }
  308.  
  309.  
  310. /*
  311.  * Delete node from hash table, and free its name.
  312.  */
  313. public void n_delete( nd )
  314.   register nptr  nd;
  315.   {
  316.     register nptr  n, *prev;
  317.  
  318.     prev = &hash[ sym_hash( pnode( nd ) ) ];
  319.     for( n = *prev; n != NULL ; n = *(prev = &n->hnext) )
  320.       {
  321.     if( n == nd )
  322.       {
  323.         Vfree( n->nname );
  324.         n->nname = NULL;
  325.         *prev = n->hnext;
  326.         n->hnext = n;        /* mark node not in hash-table */
  327.         return;
  328.       }
  329.       }
  330.   }
  331.  
  332.  
  333. /*
  334.  * Visit each node in network, calling function passed.
  335.  * If 'fun' returns anything <> 0 then terminate prematurely.
  336.  */
  337. public void walk_net( fun, arg )
  338.   int   (*fun)();
  339.   char  *arg;
  340.   {
  341.     register int   index;
  342.     register nptr  n;
  343.  
  344.     for( index = 0; index < HASHSIZE; index++ )
  345.     for( n = hash[index]; n; n = n->hnext )
  346.         if( (*fun)( n, arg ) )
  347.         return;
  348.   }
  349.  
  350.  
  351. /*
  352.  * Visit each node in network, calling function passed with arguments:
  353.  *    node    -> the current node.
  354.  *    index    -> number that identifies node in the hash-table.
  355.  *    arg    -> whatever argument the caller provided.
  356.  * If 'fun' returns FALSE then terminate prematurely.
  357.  */
  358. public void walk_net_index( fun, arg )
  359.   int   (*fun)();
  360.   char  *arg;
  361.   {
  362.     register Uint  mi, ma;
  363.     register nptr  n;
  364.  
  365.     for( ma = 0; ma < HASHSIZE; ma++ )
  366.     for( n = hash[ ma ], mi = 0; n; n = n->hnext, mi++ )
  367.       {
  368.         Ulong  val = (mi << NBIT_HASH) | ma;
  369.         if( (*fun)( n, val, arg ) )
  370.         return;
  371.       }
  372.   }
  373.  
  374.  
  375. /*
  376.  * Return a list of all nodes in the network.
  377.  */
  378. public nptr GetNodeList()
  379.   {
  380.     register int   index;
  381.     register nptr  n, *last;
  382.     struct Node    head;
  383.  
  384.     last = &(head.n.next);
  385.     for( index = 0; index < HASHSIZE; index++ )
  386.       {
  387.     for( n = hash[index]; n != NULL; n = n->hnext )
  388.       {
  389.         *last = n;
  390.         last = &(n->n.next);
  391.       }
  392.       }
  393.     *last = NULL;
  394.     return( head.n.next );
  395.   }
  396.  
  397.  
  398. /*
  399.  * Return the node corresponding to the index number (returned by Node2index).
  400.  */
  401. public nptr Index2node( index )
  402.   Ulong  index;
  403.   {
  404.     register nptr  n;
  405.     register unsigned  ma, mi;
  406.  
  407.     ma = index & ((1 << NBIT_HASH) - 1);
  408.     mi = index >> NBIT_HASH;
  409.     if( ma >= HASHSIZE )
  410.     return( NULL );
  411.     for( n = hash[ ma ]; n != NULL and mi != 0; n = n->hnext, mi-- );
  412.     return( n );
  413.   }
  414.  
  415.  
  416. /*
  417.  * Return a number that identifies the node in the name hash-table.
  418.  */
  419. public Ulong Node2index( nd )
  420.   nptr  nd;
  421.   {
  422.     register nptr      n;
  423.     register unsigned  mi, ma;
  424.     Ulong              val;
  425.  
  426.     if( nd != NULL )
  427.       {
  428.     ma = sym_hash( pnode( nd ) );
  429.     for( n = hash[ ma ], mi = 0; n != NULL; n = n->hnext, mi++ )
  430.       {
  431.         if( n == nd )
  432.         goto got_it;
  433.       }
  434.       }
  435.     ma = HASHSIZE;
  436.     mi = 0;
  437.  
  438.   got_it :
  439.     val = (mi << NBIT_HASH) | ma;
  440.     return( val );
  441.   }
  442.  
  443.  
  444. /* visit each node in network, calling function passed as arg with any node
  445.  * whose name matches pattern
  446.  */
  447. public int match_net( pattern, fun, arg )
  448.   char  *pattern;
  449.   int   (*fun)();
  450.   char  *arg;
  451.   {
  452.     register int   index;
  453.     register nptr  n;
  454.     int            total = 0;
  455.  
  456.     for( index = 0; index < HASHSIZE; index++ )
  457.     for( n = hash[index]; n; n = n->hnext )
  458.         if( str_match( pattern, pnode( n ) ) )
  459.         total += (*fun)( n, arg );
  460.  
  461.     return( total );
  462.   }
  463.  
  464.  
  465. /* return pointer to asciz name of node */
  466.  
  467. public
  468. #define    pnode( NODE )    ( (NODE)->nname )
  469.  
  470.  
  471.  
  472. /* initialize hash table */
  473. public void init_hash()
  474.   {
  475.     register int  i;
  476.  
  477.     for( i = 0; i < HASHSIZE; i += 1 )
  478.     hash[i] = NULL;
  479.   }
  480.